//
// Created by Snow on 2023/4/5.
//
#include<cstdio>
#define MaxSize 100
#define N 10		//问题涉及的人数,人的编号从1到N
#define M 7			//亲戚关系个数
#define Q 3			//询问个数
typedef struct node
{
    int data;//结点对应人的编号
    int rank;//结点对应秩
    int parent;//结点对应双亲下标
}UFSTree;//并查集树的结点类型
//并查集树的初始化
void MAKE_SET(UFSTree t[],int n)//初始化并查集树
{
    int i;
    for(i=1;i<=n;i++)
    {
        t[i].data=i;//数据为该人的编号
        t[i].rank=0;//秩初始化为0
        t[i].parent=i;//双亲初始化为自己
    }
}
//查找一个元素所属的集合
int FIND_SET(UFSTree t[],int x)//在x所在的字数中查找集合编号
{
    if(x!=t[x].parent)//双亲不是自己
        return FIND_SET(t,t[x].parent);//递归在双亲中找x
    else
        return x;//双亲是自己，返回x
}
//两个元素各自所属的结合合并
void UNION(UFSTree t[],int x,int y)//将x和y所在的字数合并
{
    x=FIND_SET(t,x);//查找x所在分离集合树的编号
    y=FIND_SET(t,y);//查找y在所分离集合树的编号
    if(t[x].rank>t[y].rank)//y结点的秩小于x结点的秩
        t[y].parent=x;//将y连接到x结点上，x作为y的双亲结点
    else//y结点的秩大于等于x结点的秩
    {
        t[x].parent=y;//将x连到y结点上，y作为x的双亲结点
        if(t[x].rank==t[y].rank)//x和y结点的秩相同
            t[y].rank++;//y结点的秩增一
    }
}
int main()
{
    int i,x,y;
    UFSTree t[MaxSize];
    int rel[M][2]={{2,4},{5,7},{1,3},{8,9},{1,2},{5,6},{2,3}};
    int ans[Q][2]={{3,4},{7,10},{8,9}};
    MAKE_SET(t,N);					//初始化并查集树t
    for (i=0;i<M;i++)				//根据关系进行合并操作
        UNION(t,rel[i][0],rel[i][1]);
    printf("data  rank  parent\n");	//输出并查集树t
    for (i=1;i<=N;i++)
        printf("%4d%5d%6d\n",t[i].data,t[i].rank,t[i].parent);
    printf("\n");
    printf("answers:\n");		//输出求解结果
    for (i=0;i<Q;i++)
    {
        x=FIND_SET(t,ans[i][0]);
        y=FIND_SET(t,ans[i][1]);
        if (x==y)
            printf("  (%d,%d):Yes\n",ans[i][0],ans[i][1]);
        else
            printf("  (%d,%d):No\n",ans[i][0],ans[i][1]);
    }
    return 1;
}